#include <iostream>
#include <vector>
using namespace std;

int max_value_recur(vector<int> &tm, vector<int> &value, int n, int t)
{
        if(n == 0){
                return 0;
        }

        int max_value = max_value_recur(tm, value, n - 1, t);
        if(tm[n] <= t){
                max_value = max(max_value, max_value_recur(tm, value, n - 1, t - tm[n]) + value[n]);
        }

        return max_value;
}

int max_value_recur(vector<int> &tm, vector<int> &value, int n, int t, vector<vector<int>> &recd)
{
        if(n == 0){
                return recd[n][t] = 0;
        }

        if(recd[n][t] != -1){
                return recd[n][t];
        }

        int max_value = max_value_recur(tm, value, n - 1, t, recd);
        if(tm[n] <= t){
                max_value = max(max_value, max_value_recur(tm, value, n - 1, t - tm[n], recd) + value[n]);
        }

        return recd[n][t] = max_value;
}

int max_value_dp(vector<int> &tm, vector<int> &value, int n, int t)
{
        vector<vector<int>> dp(n + 1, vector<int>(t + 1, 0));

        for(int i = 1; i <= n; i++){
                for(int j = 1; j <= t; j++){
                        dp[i][j] = dp[i - 1][j];
                        if(tm[i] <= j){
                                dp[i][j] = max(dp[i][j], dp[i - 1][j - tm[i]] + value[i]);
                        }
                }
        }
        return dp.back().back();
}

int max_value_dp_sp(vector<int> &tm, vector<int> &value, int n, int t)
{
        vector<int> dp(t + 1, 0);
        for(int i = 1; i <= n; i++){
                for(int j = t; j >= tm[i]; j--){
                        dp[j] = max(dp[j], dp[j - tm[i]] + value[i]);
                }
        }
        return dp.back();
}

int main()
{
        int t, n;
        cin>>t>>n;

        vector<int> tm(n + 1, 0);
        vector<int> value(n + 1, 0);
        for(int i = 1; i <= n; i++){
                cin>>tm[i]>>value[i];
        }
        vector<vector<int>> recd(n + 1, vector<int>(t + 1, -1));
        //cout<<max_value_recur(tm, value, n, t, recd)<<endl;
        cout<<max_value_dp_sp(tm, value, n, t)<<endl;
        return 0;
}
